import {buchheim, Tree} from './Tree2';
import {MinHeap} from "./Heap";

export function getTree(n,algo=0,r=0, input=[], key = 0){
    if(algo === 0)
        return buchheim(fib2(n) );
    else if( algo === 1 )
        return buchheim(ifElse(input));
    else if( algo === 3 )
        return buchheim(huffman2(input));
    else if( algo === 2 )
        return buchheim(temp());
    else if( algo === 4 )
        return buchheim(stirling2(n,r));
}

function temp() {
    let leftTree = new Tree(1, undefined, new Tree(2));

    return new Tree(0, leftTree, undefined);
}


function fib2(n) {
    let tree = new Tree(n,undefined, undefined, n+"");
    if (n < 2 ) return tree;
    tree.left = fib2(n - 1);
    tree.right = fib2(n - 2);
    tree.node = tree.left.node + tree.right.node;
    return tree;
}

function sib(n){
    let tree = new Tree(n,[]);
    if( n <3 ) return tree;
    tree.children.push( sib(n-2) );
    tree.children.push( sib(n-3) );
    tree.node = tree.children[0].node+tree.children[1].node;
    return tree;
}


function ifElseItem2(conditionList, index) {

    let tree = new Tree(index,undefined, undefined, "<" + conditionList[index]);
    let treeYes = new Tree("Yes", undefined, undefined, "Yes");
    tree.left = treeYes;
    let treeNo;
    if (index !== conditionList.length - 1) {
        treeNo = ifElseItem2(conditionList, index + 1, tree);
    } else {
        treeNo = new Tree("No", undefined, undefined, "No");
    }
    tree.right = treeNo;
    return tree;
}


function ifElse(input) {
    let conditionList = [...input];
    let tree = ifElseItem2(conditionList, 0);
    return tree;
}


function huffman2(weight) {
    // 得到权重的最小堆
    let temp = [...weight];
    let transferWeight = [];
    for (let i = 0; i < temp.length; i++) {
       if (i === 0) {
           transferWeight.push(temp[i] + "," + 0);
       } else {
           let before = transferWeight[i - 1];
           let [number, count] = before.split(",").map(x=>parseInt(x));
           if (number === temp[i]) {
               transferWeight.push(temp[i] + "," + count + 1);
           } else {
               transferWeight.push(temp[i] + "," + 0);
           }
       }
    }

    let weight_heap = new MinHeap();
    transferWeight.forEach((a) => weight_heap.insert(new Tree(a, undefined, undefined, a+ "")));
    let count = 0;
    let visited = {}
    let countNode = (key, array) => {
        let count = 0;
        for (let element of array) {
            if (element === key) {
                count ++;
            }
        }
        return count;
    }

    while (weight_heap.getLength() !== 1) {
        let tree1 = weight_heap.pop();
        let tree2 = weight_heap.pop();
        if (!(tree1.getId() in visited)) {
            tree1.setId(count++);
            visited[count-1] = true;
        }
        if (!(tree2.getId() in visited)) {
            tree2.setId(count++);
            visited[count-1] = true;
        }
        let tempHeap = [...weight_heap.heap].map(x=>parseInt(x.node.split(",")));

        let value = tree1.getNode().split(",").map(x=>parseInt(x))[0] + tree2.getNode().split(",").map(x=>parseInt(x))[0];
        let tempCount = countNode(value, tempHeap);
        let treeNode = value + "," + tempCount;

        let tree = new Tree(treeNode, tree1, tree2, treeNode);
        tree.setId(count++);
        visited[count-1] = true;
        weight_heap.insert(tree);
    }
    weight_heap.peek().setId(count);

    return weight_heap.peek();

}



function bigmod(n,r){
    if( r === 0 ) return new Tree(1,[],"("+n+","+r+")");
    if( r === 1 ) return new Tree(n,[],"("+n+","+r+")");
    let tree = new Tree(1,[],"("+n+","+r+")");
    if( r%2 === 1 ){
        tree.children.push( bigmod(n,(r-1)/2 ) );
        tree.children.push( bigmod(n,(r-1)/2) );
        tree.children.push( bigmod(n,1) );
    }else{
        tree.children.push( bigmod(n,r/2 ) );
        tree.children.push( bigmod(n,r/2) );
    }
    for(let i=0;i<tree.children.length;i++){
        tree.node *= tree.children[i].node;
    }
    return tree;
}

function stirling2(n,r){
    if( n === r ) return new Tree(1,[],"("+n+","+r+")");
    if( r === 0 ) return new Tree(0,[],"("+n+","+r+")");

    let tree = new Tree(0,[],"("+n+","+r+")");
    tree.children.push( stirling2(n-1,r) );
    tree.children.push( stirling2(n-1,r-1) );
    tree.node = tree.children[0].node*r+tree.children[1].node;
    return tree;
}